package com.zjsru.plan2025.oneday;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * 2070. 每一个查询的最大美丽值
 *
 * @Author: cookLee
 * @Date: 2025-03-09
 */
public class MaximumBeauty {

    /**
     * 主
     * 同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。
     * \
     * 输入：items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
     * 输出：[2,4,5,5,6,6]
     * 解释：
     * - queries[0]=1 ，[1,2] 是唯一价格 <= 1 的物品。所以这个查询的答案为 2 。
     * - queries[1]=2 ，符合条件的物品有 [1,2] 和 [2,4] 。
     * 它们中的最大美丽值为 4 。
     * - queries[2]=3 和 queries[3]=4 ，符合条件的物品都为 [1,2] ，[3,2] ，[2,4] 和 [3,5] 。
     * 它们中的最大美丽值为 5 。
     * - queries[4]=5 和 queries[5]=6 ，所有物品都符合条件。
     * 所以，答案为所有物品中的最大美丽值，为 6 。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        MaximumBeauty maximumBeauty = new MaximumBeauty();
        int[][] items = {{1, 2}, {3, 2}, {2, 4}, {5, 6}, {3, 5}};
        int[] queries = {1, 2, 3, 4, 5, 6};
        System.out.println(Arrays.toString(maximumBeauty.maximumBeauty2(items, queries)));
    }

    /**
     * 最大美丽
     * 时间复杂度过高
     *
     * @param items   项目
     * @param queries 查询
     * @return {@link int[]}
     */
    public int[] maximumBeauty(int[][] items, int[] queries) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int[] item : items) {
            map.put(item[0], Math.max(map.getOrDefault(item[0], 0), item[1]));
        }
        int[] ans = new int[queries.length];
        Arrays.fill(ans, 0);
        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            //从最大值开始往下找
            for (int j = query; j >= 0; j--) {
                if (map.containsKey(j)) {
                    Integer value = map.get(j);
                    ans[i] = Math.max(value, ans[i]);
                }
            }
        }
        return ans;
    }

    public int[] maximumBeauty2(int[][] items, int[] queries) {
        Arrays.sort(items, (a, b) -> a[0] - b[0]);
        Integer[] idx = new Integer[queries.length];
        Arrays.setAll(idx, i -> i);
        Arrays.sort(idx, Comparator.comparingInt(i -> queries[i]));

        int[] ans = new int[queries.length];
        int j = 0;
        int max = 0;
        for (int i : idx) {
            while (j < items.length && items[j][0] <= queries[i]) {
                max = Math.max(max, items[j][1]);
                j++;
            }
            ans[i] = max;
        }
        return ans;
    }
}
